This invention relates generally to computer graphics and more particularly to the representation of an input image by an output device.
As it is known in the art, digital halftoning is a process of generating a pattern of binary pixels that is representative of a given input image. Much effort has been made in the field of halftoning to ensure that the output image is a pleasing representative of the input image and possesses minimal visual side-effects, such as repeating structures, which impart an unnatural appearance to the resulting output image.
Digital halftoning is used to represent an input image comprising a number of picture elements (referred to in the art as xe2x80x98pixelsxe2x80x99) on an output device. Typically digital halftoning is used when the output device is not capable of representing each of the color values of the input image, where here color refers to either the chrominance or luminance value of the input image. For example, in the case of printing monochrome images, the number of input levels is 256 and the number of output levels is 2. By varying the ratio of black pixels to white pixels throughout the output image, the effect of 256 color levels is achieved.
One technique for providing a halftoned image is through ordered dithering. Ordered dithering uses a dither matrix, which is an array of integer threshold values, to produce the shaded output image. The dither matrix is commonly smaller than the input image, and is repeatedly tiled over the input image. Each color value of the input image is compared against a dither matrix threshold value. When the input value is greater than the threshold value, the output pixel is turned xe2x80x9conxe2x80x9d, if the input value of the pixel is less than or equal to the threshold value, the output pixel is turned xe2x80x9coffxe2x80x9d. Because the dither matrix thresholds essentially determine which pixels of the input image are displayed on the output device, the ordering of the threshold values in the dither matrix is important to the quality of the output image.
Various processes for arranging threshold values within a dither matrix have been developed. One method for assigning dither matrix threshold values is described in U.S. patent application Ser. No. 07/961,244 U.S. Pat. No. 5,538,020, entitled xe2x80x9cVoid and Cluster Apparatus and Method for Generating Dither Templatesxe2x80x9d, filed Oct. 15, 1992 by Robert A. Ulichney (hereinafter referred to as the void and cluster patent). According to the process disclosed in the void and cluster patent, threshold values are assigned according to a characteristic of a pixel stored in a corresponding location of a homogeneously distributed pattern of binary elements. Accordingly, because threshold values are assigned through the use of a homogeneously distributed pattern of binary elements, an output image provided using the void and cluster dither matrix possesses few low frequency spatial characteristics, and is therefore visually pleasing.
The void and cluster method of providing dither matrix threshold values is a significant advancement over the compute intensive methods of the prior art which required numerous iterations and neighborhood calculations to achieve a less visually pleasing result.
While all dithering processes aim to provide a visually pleasing image, the result is not always achieved. A performance loss arises because virtually all halftoning methods assume a perfect square printer dot as the output dot. However, the printer dots produced by a printer vary in size depending upon the individual characteristics of the printer. As a result, printed images halftoned with the above described processes may be distorted versions of the original image. Traditionally, an attempt is made to remove printer-based distortions via measurement-based techniques known as tone correction which calibrate a halftoning method for a each specific printer.
Referring now to FIG. 1A, a graph plotting the measured output values provided by a typical halftoned system versus the desired output values illustrates the need for tone correction of the output image. The amount by which the output pixel value differs from the desired value is the tone error of the output image. In the case of hardcopy, the tone error may be determined by measuring an output image with a device referred to as a reflection densitometer. A tone characteristic curve, y=f(x), such as that shown in FIG. 1A, is derived by plotting the measured value against the desired value and normalizing the ranges to be between 0 and 1.
Once the tone error of the output image is determined, a prior art method of correcting the output image included deriving the inverse function, y=fxe2x88x921(x) of the tone characteristic curve, as shown in FIG. 1B. The inverse characteristic curve is used to map input pixel levels to adjusted pixel levels. Accordingly, the input level is compensated for the tone error of the output device prior to the dithering of the input image.
One drawback of the above described tone correction method is that it reduces performance of the graphics system because it requires an additional mapping operation to be performed on every input pixel. Another drawback of the above described method is the loss of fidelity of the output image. The loss of fidelity arises, as shown in FIG. 1B, because in some portions of the curve the slope is less than one. When the slope is less than one, more than one input pixel level maps to the same adjusted pixel level. The result is a loss of input representation levels of the input image and accordingly a loss of fidelity of the image.
According to one aspect of the invention, a method of providing an output image for display on an output device representative of an input image, includes the steps of generating a dither array comprising a plurality of threshold values, adjusting the threshold values of the dither array in accordance with a tone characteristic of the output device, and comparing the adjusted dither template values against the input image pixels to determine which input image pixels are to be displayed on the output device. With such an arrangement, the overall performance of the graphics system is increased because the tone correction of an input image may be compensated for in the dither template, and a separate operation need not be performed on each input image pixel by the graphics system.
According to a further aspect of the invention, the plurality of threshold values of the dither template exceeds said representation levels of said input device, and the step of providing an output image further includes the step of normalizing the adjusted threshold values of said dither template prior to comparing the adjusted dither template values to the input image pixels. With such an arrangement, the fidelity of the output system is increased because providing a large number of threshold values in the dither template allows for a one to one mapping of tone adjusted pixels to expected pixels of the input device.